#define  _CRT_SECURE_NO_WARNINGS
class Solution {
    int m;
    int n;
    int bfs(vector<vector<int>>& forest, int tgt, int cr, int cc)
    {
        if (forest[cr][cc] == tgt) return 0;
        vector<vector<bool>> visit(m, vector<bool>(n, false));
        queue<pair<int, int>> q;
        int ret = 0;
        q.push({ cr, cc });
        visit[cr][cc] = true;
        while (q.size())
        {
            ret++;
            int sz = q.size();
            while (sz--)
            {
                auto [r, c] = q.front(); q.pop();
                static int dx[4] = { 1,-1,0,0 };
                static int dy[4] = { 0,0,1,-1 };
                for (int i = 0; i < 4; i++)
                {
                    int x = r + dx[i];
                    int y = c + dy[i];
                    if (x >= 0 && x < m && y >= 0 && y < n
                        && forest[x][y] && !visit[x][y])
                    {
                        if (forest[x][y] == tgt)
                        {
                            forest[x][y] = 1;
                            return ret;
                        }
                        visit[x][y] = true;
                        q.push({ x, y });
                    }
                }
            }
        }
        return -1;
    }

public:
    int cutOffTree(vector<vector<int>>& forest) {
        map<int, pair<int, int>> hash;
        m = forest.size(), n = forest[0].size();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (forest[i][j] > 1) hash[forest[i][j]] = { i, j };

        int sum = 0, x = 0, y = 0;
        for (auto e : hash)
        {
            int tgt = e.first;
            int ret = bfs(forest, tgt, x, y);
            if (ret == -1) return -1;
            sum += ret;
            x = e.second.first;
            y = e.second.second;
            forest[x][y] = 1;
        }
        return sum;
    }
};

